#ifndef VL_VECTOR_HPP
#define VL_VECTOR_HPP

#include <cstdlib>
#include <cstring>
#include <cassert>
#include <new>
#include "common.hpp"
#include "move.hpp"
#include <algorithm>

namespace vl
{

template<class T>
struct vector
{
	typedef T* iterator;

	vector()
	: _size(0), _capacity(0), _first(0)
	{
	}

	vector(size_t s, T const& v = T())
	{
		alloc_first_(s, v);
	}

	vector(T const* p, size_t len)
	: _size(len)
	{
		alloc_(len);
		memcpy(_first, p, sizeof(T) * _size);
	}

	vector(vector const& b)
	: _size(b._size)
	{
		alloc_(max(_size, 16u));
		for(size_t i = 0; i < _size; ++i)
		{
			new (_first + i) T(b._first[i]);
		}
	}

	vector(move_tag, vector& b)
	: _size(b._size), _first(b._first), _capacity(b._capacity)
	{
		b._size = 0;
		b._capacity = 0;
		b._first = 0;
	}

	vector(move<vector>& b)
	: _size(b->_size), _first(b->_first), _capacity(b->_capacity)
	{
		b->_size = 0;
		b->_capacity = 0;
		b->_first = 0;
	}

	~vector()
	{
		destroy_();
		free(_first);
	}

	void push_back(T const& v)
	{
		cons_(push_back_raw_(), v);
	}

	simple_construct<T> push_back_inplace()
	{
		return push_back_raw_();
	}

/*
	template<class T1>
	void push_back_inplace(T1 const& p1)
	{
		new (push_back_raw_()) T(p1);
	}

	template<class T1, class T2>
	void push_back_inplace(T1 const& p1, T2 const& p2)
	{
		new (push_back_raw_()) T(p1, p2);
	}
*/
	void insert(size_t pos, vector const& b)
	{
		size_t count = b.size();
		ensure_space_(count);

		// Move [pos, size()) count steps forward
		memmove(_first + (pos + count), _first + pos, sizeof(T) * (size() - pos));
		copy_(pos, pos + count, &b[0]);
		_size += count;
	}
	
	void insert(size_t pos, size_t count = 1, T const& v = T())
	{
		ensure_space_(count);

		// Move [pos, size()) count steps forward
		memmove(_first + (pos + count), _first + pos, sizeof(T) * (size() - pos));
		cons_(pos, pos + count, v);
		_size += count;
	}
	
	T* push_back_raw(size_t count = 1)
	{
		ensure_space_(count);
		T* p = _first + _size;
		_size += count;
		return p;
	}
	
	T* push_back_raw(size_t count, T*& adjust)
	{
		ensure_space_(count, adjust);
		T* p = _first + _size;
		_size += count;
		return p;
	}
	
	void pop_back_raw(size_t count = 1)
	{
		assert(_size >= count);
		_size -= count;
	}

	simple_construct<T> insert_inplace(size_t pos)
	{
		ensure_space_();

		// Move [pos, size()) count steps forward
		memmove(_first + (pos + 1), _first + pos, sizeof(T) * (size() - pos));
		++_size;
		return simple_construct<T>(_first + pos);
	}

	void insert(size_t pos, T const& v = T())
	{
		insert(pos, 1, v);
	}

	void erase(size_t pos, size_t amount = 1)
	{
		T* base = _first + pos;
		for(size_t i = 0; i < amount; ++i)
		{
			(base + i)->~T();
		}
		memmove(_first + pos, _first + pos + amount, sizeof(T) * (size() - pos - amount));
		_size -= amount;
	}

	T& operator[](size_t pos)
	{
		return _first[pos];
	}

	T const& operator[](size_t pos) const
	{
		return _first[pos];
	}

	T& back()
	{
		return _first[_size - 1];
	}

	T& front()
	{
		return _first[0];
	}

	size_t size() const
	{
		return _size;
	}

	size_t capacity() const
	{
		return _capacity;
	}

	void clear()
	{
		destroy_();
		realloc_(16);
		_size = 0;
	}

	void assign(size_t s, T const& v = T())
	{
		destroy_();
		assign_first_(s, v);
	}

	bool empty() const
	{
		return _size == 0;
	}

	void swap(vector& b)
	{
		swap(_first, b._first);
		swap(_size, b._size);
		swap(_capacity, b._capacity);
	}
	
	void move_to(vector& b)
	{
		b.destroy_();
		std::free(b._first);
		//b._size = 0;
		
		b._first = _first;
		b._size = _size;
		b._capacity = _capacity;
		_first = 0;
		_size = 0;
		_capacity = 0;
	}

	bool operator==(vector const& b) const
	{
		if(_size != b._size)
			return false;

		for(size_t i = 0; i < _size; ++i)
		{
			if(_first[i] != b._first[i])
				return false;
		}

		return true;
	}

	bool operator!=(vector const& b) const
	{
		return !operator==(b);
	}
	
	T* begin()
	{
		return _first;
	}
	
	T* end()
	{
		return _first + _size;
	}

private:
	void* push_back_raw_()
	{
		ensure_space_();

		assert(_size < _capacity);
		void* v = _first + _size;
		++_size;
		return v;
	}

	void assign_first_(size_t s, T const& v = T())
	{
		size_t c = max(s, 16u);
		realloc_(c);
		_size = s;
		cons_(0, s, v);
	}

	void alloc_first_(size_t s, T const& v = T())
	{
		size_t c = max(s, 16u);
		alloc_(c);
		_size = s;
		cons_(0, s, v);
	}

	void alloc_(size_t c)
	{
		_first = static_cast<T *>(malloc(sizeof(T) * c));
		_capacity = c;
	}

	void realloc_(size_t c)
	{
		_first = static_cast<T *>(realloc(_first, sizeof(T) * c));
		_capacity = c;
	}

	void cons_(size_t a, size_t b, T const& v = T())
	{
		for(size_t i = a; i < b; ++i)
			cons_(_first + i, v);
	}

	void cons_(void* p, T const& v = T())
	{
		new (p) T(v);
	}
	
	void copy_(size_t a, size_t b, T* src)
	{
		for(size_t i = a; i < b; ++i)
			cons_(_first + i, *src++);
	}

	void destroy_()
	{
		for(size_t i = 0; i < _size; ++i)
		{
			(_first + i)->~T();
		}
	}

	void inc_capacity_(size_t m)
	{
		realloc_(max((_capacity * 3 + 1) / 2, m));
	}

	void inc_capacity_()
	{
		realloc_((_capacity * 3 + 1) / 2);
	}

	void ensure_space_(size_t count)
	{
		if(_size + count > _capacity)
		{
			inc_capacity_(_size + count);
		}
	}
	
	void ensure_space_(size_t count, T*& adjust)
	{
		if(_size + count > _capacity)
		{
			T* old = _first;
#ifndef NDEBUG
			int offs = (adjust - _first);
			assert(offs >= 0);
#endif
			inc_capacity_(_size + count);
			adjust += (_first - old);
			
			assert(_first + offs == adjust);
		}
	}

	void ensure_space_()
	{
		if(_size >= _capacity)
		{
			inc_capacity_(8);
		}
	}

	T* _first;
	size_t _size;
	size_t _capacity;
};

}

#endif //VL_VECTOR_HPP
